package dp;

public class _15_377_组合总和Ⅳ {
    public static int combinationSum4(int[] nums, int target) {
    	int dp[] = new int[target+1];
    	dp[0] = 1;
    	// 求全排列满足条件有多少种
    	// 我们之前求组合的时候是先遍历物品再遍历背包
    	// 求全排列只需要先遍历背包再遍历物品即可
    	for(int j = 0; j <= target; j++) {
    		for(int i = 0; i < nums.length; i++) {
    			if(j >= nums[i]) {
    				dp[j] += dp[j - nums[i]];
    			}
    		}
    	}
    	
    	return dp[target];
    }
    
    public static void main(String[] args) {
		int nums[] = {1,2,3};
		System.out.println(combinationSum4(nums, 4));
	}
}
